package com.mzy;

import com.mzy.utils.Utils;
import sun.nio.cs.UTF_32LE;
import sun.nio.cs.ext.IBM300;

import java.nio.channels.Channel;
import java.nio.channels.SelectionKey;
import java.nio.channels.Selector;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Set;
import java.util.concurrent.BlockingDeque;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.LinkedBlockingDeque;

import static com.mzy.utils.Utils.swap;

/**
 * @Author: codermzy
 * @Date: 2024/04/27/下午1:27
 * @Description:
 */
public class HeapSort {

    /*public static void heapSort(Integer[] arr) {

        // 1. 对数组进行原地建堆
        //      获取第一个非叶子节点，然后对其进行下滤操作
        int n = arr.length;
        int start = (n >> 1) - 1;
        for (int i = start; i >= 0; i--) {
            heapifyDown(arr, n, i);
        }

        // 2. 对当前最大堆进行排序
        // 将第0项和第n - 1项交换，此时 n - 1 项就是最大值，维护对大堆，第 0 项进行下滤
        // 将第0项和第n - 2项交换，此时 n - 2 项就是次大值
        // 依次类推
        for (int i = n - 1; i > 0; i--) {
            Utils.swap(arr, 0, i);
            heapifyDown(arr, i, 0);
        }

    }

    private static void heapifyDown(Integer[] arr, int n, int index) {

        while (index * 2 + 1 < n) {
            // 获取当前节点的左子节点和右子节点
            int leftChildrenIndex = index * 2 + 1;
            int rightChildrenIndex = index * 2 + 2;

            int largeChildrenIndex = leftChildrenIndex;

            if (largeChildrenIndex < n && rightChildrenIndex < n && arr[rightChildrenIndex] > arr[largeChildrenIndex]) {
                largeChildrenIndex = rightChildrenIndex;
            }

            if (arr[index] > arr[largeChildrenIndex]) {
                break;
            }

            Utils.swap(arr, index, largeChildrenIndex);
            index = largeChildrenIndex;
        }
    }
*/

    public static void main(String[] args) {
        Integer[] arr = {10, 14, 18, 32, 60, 25, 70, 67, 5, 55};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
        //
        Utils.testSort(HeapSort::heapSort);
    }

    private static void heapSort(Integer[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapifyDown(arr, i, arr.length);
        }

        for (int i = arr.length - 1; i >= 0; i--) {
            swap(arr, 0, i);
            heapifyDown(arr, 0, i);
        }
    }

    private static void heapifyDown(Integer[] arr, int i, int length) {
        while (i * 2 + 1 < length) {
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            int large = left;

            if (right < length && arr[large] < arr[right]) {
                large = right;
            }
            if (arr[large] < arr[i]) {
                break;
            }
            swap(arr, i, large);
            i = large;
        }
    }

    /*private static void heapSort(Integer[] arr) {
        // 堆化
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapifyDown(arr, i, arr.length);
        }

        // 堆排，交换
        for (int i = arr.length - 1; i >= 0; i--) {
            swap(arr, 0, i);
            heapifyDown(arr, 0, i);
        }
    }

    private static void heapifyDown(Integer[] arr, int i, int length) {
        while (i * 2 + 1 < length) {
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            int large = left;

            if (right < length && arr[large] < arr[right]) {
                large = right;
            }

            if (arr[large] <= arr[i]) {
                break;
            }

            swap(arr, i, large);
            i = large;
        }
    }*/

/*    private static void heapSort(Integer[] arr) {
        // 堆化
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapifyDown(arr, i, arr.length);
        }
        System.out.println(Arrays.toString(arr));
        // 排序交换第一个元素和最后一个，然后进行下滤
        // for (int i = arr.length - 1; i >= 0; i--) {
        //     swap(arr, 0, i);
        //     heapifyDown(arr, 0, i);
        // }
    }

    private static void heapifyDown(Integer[] arr, int i, int length) {
        while (i * 2 + 1 < length) {
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            int large = left;

            if (right < length && arr[large] > arr[right]) {
                large = right;
            }
            if (arr[large] > arr[i]) {
                break;
            }
            swap(arr, i, large);
            i = large;
        }
    }*/

    /*private static void heapSort(Integer[] arr) {
        // 堆化
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapifyDown(arr, i, arr.length);
        }

        // 交换第0和n-1的元素，然后对0到n-1的元素下滤
        // 交换第1和n-2的元素，然后对0到n-2的元素下滤
        for (int i = arr.length - 1; i >= 0; i--) {
            swap(arr, 0, i);
            heapifyDown(arr, 0, i);
        }
    }

    private static void heapifyDown(Integer[] arr, int i, int length) {
        while (i * 2 + 1 < length) {
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            int large = left;
            if (right < length && arr[large] < arr[right]) {
                large = right;
            }
            if (arr[large] < arr[i]) {
                break;
            }
            swap(arr, large, i);
            i = large;
        }
    }*/
    /*

    private static void heapSort(Integer[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapifyDown(arr, i, arr.length);
        }

        for (int i = arr.length - 1; i >= 0; i--) {
            swap(arr, 0, i);
            heapifyDown(arr, 0, i);

        }
    }

    private static void heapifyDown(Integer[] arr, int i, int length) {
        while (i * 2 + 1 < length) {
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            int large = left;

            if (right < length && arr[large] < arr[right]) {
                large = right;
            }

            if (arr[i] > arr[large]) {
                break;
            }

            swap(arr, i, large);
            i = large;
        }
    }
    */

/*    private static void heapSort(Integer[] arr) {
        // 原地建堆
        for (int i = (arr.length / 2) - 1; i >= 0; i--) {
            heapifyDown(arr, i, arr.length);
        }

        // 将第0个元素和 n - 1 位置的元素交换
        for (int i = arr.length - 1; i >= 0; i--) {
            swap(arr, 0, i);
            heapifyDown(arr, 0, i);
        }
    }

    private static void heapifyDown(Integer[] arr, int i, int length) {
        while (i * 2 + 1 < length) {
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            int large = left;

            if (right < length && arr[large] < arr[right]) {
                large = right;
            }
            if (arr[large] <= arr[i]) {
                break;
            }

            swap(arr, i, large);
            i = large;
        }
    }*/
/*
    private static void heapSort(Integer[] arr) {

        for (int i = (arr.length / 2) - 1; i >= 0; i--) {
            heapifyDown(arr, i, arr.length);
        }

        for (int i = arr.length - 1; i >= 0; i--) {
            swap(arr, 0, i);
            heapifyDown(arr, 0, i);
        }
    }

    private static void heapifyDown(Integer[] arr, int i, int length) {
        while (i * 2 + 1 < length) {
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            int large = left;
            if (right < length && arr[large] < arr[right]) {
                large = right;
            }

            if (arr[i] > arr[large]) {
                break;
            }
            swap(arr, i, large);
            i = large;
        }
    }
    */

   /* private static void heapSort(Integer[] arr) {
        // 原地建堆
        for (int i = (arr.length / 2) - 1; i >= 0; i--) {
            heapifyDown(arr, i, arr.length);
        }

        // 将第 1 个值弹出，然后放到最后一个位置

        for (int i = arr.length - 1; i >= 0; i--) {
            Utils.swap(arr, 0, i);
            heapifyDown(arr, 0, i);
        }
    }


    }*/

    /*private static void heapSort(Integer[] arr) {
        // 先进行原地建堆
        // 从最后一个非叶子节点开始，依次执行下滤操作
        for (int i = (arr.length / 2) - 1; i >= 0; i--) {
            heapifyDown(arr, i, arr.length);
        }

        // 进行堆排序
        // 将第0项和n-1项进行交换，然后对第0项进行下滤操作，维护最大堆
        for (int i = arr.length - 1; i >= 0; i--) {
            swap(arr,0, i);
            heapifyDown(arr, 0, i);
        }
    }

 */

/*    private static void heapifyDown(Integer[] arr, int index, int length) {
        while (index * 2 + 1 < length) {
            int left = index * 2 + 1;
            int right = index * 2 + 2;
            int large = left;

            if (large < length && right < length && arr[large] < arr[right]) {
                large = right;
            }
            if (arr[index] >= arr[large]) {
                break;
            }
            Utils.swap(arr, large, index);
            index = large;
        }
    }*/
}

